package cn.bellychang.wangzheng.bitmap;

/**
 * @author ChangLiang
 * @date 2021/2/20
 */
public class BitMap {

    // java中char类型占用16bit 即2个字节

    /**
     * 位图通过数组下标来定位数据，所以效率非常高
     * 而且，每个数字用一个二进制位来表示，在数字范围不大的情况下，所需要的内存空间非常节省。
     */
    private char[] bytes;
    private int nbits;

    public BitMap(int nbits){
        this.nbits = nbits;
        this.bytes = new char[nbits / 16 + 1];
    }

    public void set(int k) {
        if (k > nbits) {
            return;
        }
        // 表示是第几个byte
        int byteIndex = k / 16;
        // 表示byte中第几个bit
        int bitIndex = k % 16;
        // 将1左移bitIndex位 因为存储是从0开始的 做或运算
        bytes[byteIndex] |= (1 << bitIndex);
    }

    public boolean get(int k) {
        if (k > nbits) {
            return false;
        }
        int byteIndex = k / 16;
        int bitIndex = k % 16;
        // 做与运算
        return (bytes[byteIndex] & (1 << bitIndex)) != 0;
    }
}
